﻿using System;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Drawing2D;
using System.Linq;
using System.Text;
using System.Threading;
using System.Windows;
using DiscoveryLogic.Common.Utilities;
using DiscoveryLogic.DataViz.NetworkDiagram.LinkerControls;
using Point=System.Drawing.Point;

namespace DiscoveryLogic.DataViz.NetworkDiagram.Layouts
{
    /// <summary>
    /// 
    /// </summary>
    public class ForceDirectedLayout : IGraphLayout
    {
        #region events 
        public event OnGraphUpdated GraphUpdated;
        public event OnGraphLayoutFinished GraphLayoutFinished;
        #endregion

        #region fields
        private Graph _Graph;
        // private Graphics _Graph;
        private Bitmap img;
        private Dictionary<Guid, Vector> verticeForces;
        private Mutex _SyncObj;
        // network name -> scale factor 
        private Dictionary<string,double> _DistanceScaleFactor = new Dictionary<string, double>();
        private Dictionary<NetworkJoin, double> _DistanceScaleFactor2=new Dictionary<NetworkJoin, double>();
        private bool _IsStopped = false;
        private int _Iteration;
        private Thread _WorkerThread;
        private List<Guid> _OrphanedVerticeIDs=new List<Guid>();
        private List<Guid> _SelectedVerticeIDs=new List<Guid>();
        private List<Guid> _SelectedEdgeIDs = new List<Guid>();
        #endregion

        #region props

        /// <summary>
        /// 
        /// </summary>
        public Graph Graph
        {
            get
            {
                return _Graph;
            }
        }

        private double _RefreshFrequency = 1.0;
        /// <summary></summary>
        public double RefreshFrequency
        {
            get
            {
                return this._RefreshFrequency;
            }
            set
            {
                this._RefreshFrequency = value;
            }
        }

        private double _SpringStiffness = 2.0;
        /// <summary></summary>
        public double SpringStiffness
        {
            get
            {
                return this._SpringStiffness;
            }
            set
            {
                this._SpringStiffness = value;
            }
        }

        private double _ElectronicRepulsionFactor = 20.0;
        /// <summary></summary>
        public double ElectronicRepulsionFactor
        {
            get
            {
                return this._ElectronicRepulsionFactor;
            }
            set
            {
                this._ElectronicRepulsionFactor = value;
            }
        }

        /// <summary>
        /// 
        /// </summary>
        public bool IsStopped
        {
            get
            {
                return _IsStopped;
            }
        }

        /// <summary>
        /// rendered image
        /// </summary>
        public Image Diagram
        {
            get
            {
                return img;
            }
        }

        /// <summary>
        /// 
        /// </summary>
        public List<Vertice> SelectedVertices
        {
            get
            {
                if(this._SelectedVerticeIDs !=null && this._SelectedVerticeIDs.Count>0)
                {
                    List<Vertice> selectedVs=new List<Vertice>();
                    foreach(Guid selectedID in this._SelectedVerticeIDs)
                    {
                        if (this._Vertices.ContainsKey(selectedID))
                            selectedVs.Add(this._Vertices[selectedID]);
                    }
                    return selectedVs;
                }
                else
                    return null;
            }
        }

        /// <summary>
        /// 
        /// </summary>
        public List<Edge> SelectedEdges
        {
            get
            {
                if(this._SelectedEdgeIDs !=null && this._SelectedEdgeIDs.Count>0)
                {
                    List<Edge> selectedEs=new List<Edge>();
                    foreach(Guid selectedID in this._SelectedEdgeIDs)
                    {
                        selectedEs.Add(this._Edges[selectedID]);
                    }
                    return selectedEs;
                }
                else
                    return null;
            }
        }

        #endregion

        #region arrow

        private float _ArrowWidth = 8f;
        /// <summary></summary>
        public float ArrowWidth
        {
            get
            {
                return this._ArrowWidth;
            }
            set
            {
                this._ArrowWidth = value;
            }
        }

        private float _ArrowTheta = 0.5f;
        /// <summary></summary>
        public float ArrowTheta
        {
            get
            {
                return this._ArrowTheta;
            }
            set
            {
                this._ArrowTheta = value;
            }
        }
        #endregion

        #region init

        /// <summary>
        /// 
        /// </summary>
        /// <param name="size"></param>
        /// <param name="graph"></param>
        public void Init(SizeF size, Graph graph)
        {
            this._GraphSize = size;
            this._Graph = graph;
            this._BackColor = Color.White;
            this._Vertices = graph.Vertices;
            this._Edges = new Dictionary<Guid, Edge>();
            Dictionary<string, Range<float>> distanceRangesByNetwork=new Dictionary<string, Range<float>>();
            Dictionary<NetworkJoin, Range<float>> distanceRangesByJoin=new Dictionary<NetworkJoin, Range<float>>();
            List<double> distances = new List<double>();
            foreach (Edge e in graph.Edges.Values)
            {
                distances.Add(e.Length);
            }
            double cutoffDistance = StatsUtil.GetLowPercentile(distances, this._DistancePercentileCutoff).Value;
            foreach (Edge e in graph.Edges.Values)
            {
                if (e.VerticeID1 == e.VerticeID2)
                    continue;

                if (e.Length <= cutoffDistance && e.Length <= this._DistanceThreshold)
                {
                    this._Edges.Add(e.ID, e);
                    Vertice v1 = this._Vertices[e.VerticeID1];
                    Vertice v2 = this._Vertices[e.VerticeID2];
                    if (v1.NetworkName == v2.NetworkName)
                    {
                        if (distanceRangesByNetwork.ContainsKey(v1.NetworkName))
                        {
                            Range<float> range = distanceRangesByNetwork[v1.NetworkName];
                            if (e.Length < range.FromValue)
                                range.FromValue = e.Length;
                            else if (e.Length > range.ToValue)
                                range.ToValue = e.Length;
                            distanceRangesByNetwork[v1.NetworkName] = range;
                        }
                        else
                        {
                            Range<float> range = new Range<float>(e.Length, e.Length);
                            distanceRangesByNetwork.Add(v1.NetworkName, range);
                        }
                    }
                    else
                    {
                        foreach(NetworkJoin join in this._Graph.Joins)
                        {
                            if((join.FromNetworkName==v1.NetworkName && join.ToNetworkName==v2.NetworkName) ||
                                (join.FromNetworkName == v2.NetworkName && join.ToNetworkName == v1.NetworkName))
                            {
                                if (distanceRangesByJoin.ContainsKey(join))
                                {
                                    Range<float> range = distanceRangesByJoin[join];
                                    if (e.Length < range.FromValue)
                                        range.FromValue = e.Length;
                                    else if (e.Length > range.ToValue)
                                        range.ToValue = e.Length;
                                    distanceRangesByJoin[join] = range;
                                }
                                else
                                {
                                    Range<float> range = new Range<float>(e.Length, e.Length);
                                    distanceRangesByJoin.Add(join, range);
                                }
                                break;
                            }
                        }
                    }
                }
            }
           
            this._DistanceScaleFactor=new Dictionary<string, double>();
            foreach(string networkName in distanceRangesByNetwork.Keys)
            {
                Range<float> range = distanceRangesByNetwork[networkName];
                if (range.ToValue > Math.Max(size.Width, size.Height))
                {
                    this._DistanceScaleFactor.Add(networkName, Math.Max(size.Width, size.Height)/range.ToValue);
                }
                else
                {
                    this._DistanceScaleFactor.Add(
                        networkName,
                        Math.Max(size.Width, size.Height)/(range.ToValue*Math.Sqrt(this._Vertices.Count)));
                }
            }
            this._DistanceScaleFactor2=new Dictionary<NetworkJoin, double>();
            foreach(NetworkJoin join in this._Graph.Joins)
            {
                Range<float> range = distanceRangesByJoin[join];
                if (range.ToValue > Math.Max(size.Width, size.Height))
                {
                    this._DistanceScaleFactor2.Add(join, Math.Max(size.Width, size.Height) / range.ToValue);
                }
                else
                {
                    this._DistanceScaleFactor2.Add(
                        join,
                        Math.Max(size.Width, size.Height) / (range.ToValue * Math.Sqrt(this._Vertices.Count)));
                }
            }
            
            this._LayoutAlgorithm = GraphLayoutAlgorithm.FruchtermanReingold;
            this._SyncObj = new Mutex(false, "GraphLayout");
            // set initial position for non-connected vertices to the edge of screen
            this._OrphanedVerticeIDs=new List<Guid>();
            foreach(Guid vID in this._Vertices.Keys)
            {
                bool isConnected = false;
                foreach(Edge e in this._Edges.Values)
                {
                    if(e.VerticeID1==vID || e.VerticeID2==vID)
                    {
                        isConnected = true;
                        break;
                    }
                }
                if (!isConnected)
                    this._OrphanedVerticeIDs.Add(vID);
            }
            if(this._OrphanedVerticeIDs.Count>0)
            {
                int topCount = (int) (this._OrphanedVerticeIDs.Count*this._GraphSize.Width/
                                      (this._GraphSize.Width*2 + this._GraphSize.Height*2));
                int rightCount = (int) (this._OrphanedVerticeIDs.Count*(this._GraphSize.Width + this._GraphSize.Height)/
                                        (this._GraphSize.Width*2 + this._GraphSize.Height*2));
                int bottomCount = topCount;
                int leftCount = this._OrphanedVerticeIDs.Count - topCount - bottomCount - rightCount;

                for(int i=0;i<this._OrphanedVerticeIDs.Count;i++)
                {
                    float x = 0;
                    float y = 0;
                    Guid orphanedVID = this._OrphanedVerticeIDs[i];
                    Vertice orphanedV = this._Vertices[orphanedVID];
                    if(i<topCount)
                    {
                        y = 0;
                        if (topCount > 0)
                            x = i*(this._GraphSize.Width/topCount);
                    }
                    else if(i<topCount + rightCount)
                    {
                        x = this._GraphSize.Width;
                        if (rightCount > 0)
                            y = (i - topCount)*(this._GraphSize.Height/rightCount);
                    }
                    else if(i<topCount + rightCount + bottomCount)
                    {
                        x = this._GraphSize.Width;
                        y = this._GraphSize.Height;
                        if (bottomCount > 0)
                            x -= (i - topCount - rightCount)*(this._GraphSize.Width)/bottomCount;
                    }
                    else
                    {
                        x = 0;
                        y = this._GraphSize.Height;
                        if(leftCount>0)
                            y -= (i - topCount - rightCount - bottomCount)*this._GraphSize.Height/leftCount;
                    }
                    orphanedV.PosX = x;
                    orphanedV.PosY = y;
                }
            }
        }
        #endregion

        #region Implementation of IGraphLayout

        private GraphLayoutAlgorithm _LayoutAlgorithm;
        /// <summary>
        /// 
        /// </summary>
        public GraphLayoutAlgorithm LayoutAlgorithm
        {
            get { return _LayoutAlgorithm; }
            set { _LayoutAlgorithm=value; }
        }

        private int _MaxIterations=10000;
        /// <summary>
        /// 
        /// </summary>
        public int MaxIteration
        {
            get { return _MaxIterations;}
            set { _MaxIterations=value; }
        }

        private SizeF _GraphSize;
        /// <summary>
        /// 
        /// </summary>
        public SizeF GraphSize
        {
            get { return _GraphSize; }
            set { _GraphSize=value; }
        }

        private Color _BackColor;
        /// <summary>
        /// 
        /// </summary>
        public Color BackgroundColor
        {
            get { return _BackColor; }
            set { _BackColor=value; }
        }

        private Dictionary<Guid, Vertice> _Vertices;
        /// <summary>
        /// 
        /// </summary>
        public Dictionary<Guid, Vertice> Vertices
        {
            get { return _Vertices; }
            set { _Vertices=value; }
        }

        private Dictionary<Guid, Edge> _Edges;
        /// <summary>
        /// 
        /// </summary>
        public Dictionary<Guid, Edge> Edges
        {
            get { return _Edges; }
            set { _Edges=value; }
        }

        private bool _ShowVerticeLabels;
        /// <summary>
        /// 
        /// </summary>
        public bool ShowVerticeLabels
        {
            get { return _ShowVerticeLabels; }
            set { _ShowVerticeLabels=value; }
        }

        private bool _ShowEdgeDistances;
        /// <summary>
        /// 
        /// </summary>
        public bool ShowEdgeDistances
        {
            get { return _ShowEdgeDistances; }
            set { _ShowEdgeDistances=value; }
        }

        private double _DistanceThreshold = double.MaxValue;
        /// <summary>
        /// 
        /// </summary>
        public double DistanceThreshold
        {
            get { return _DistanceThreshold; }
            set { _DistanceThreshold=value; }
        }

        private int _DistancePercentileCutoff = 100;
        /// <summary>
        /// value of 10 means shortest 10% edges are kept, others are skipped
        /// </summary>
        public int DistancePercentileCutoff
        {
            get { return _DistancePercentileCutoff; }
            set { _DistancePercentileCutoff=value; }
        }

        /// <summary>
        /// 
        /// </summary>
        public void StartRender(bool asyncMode)
        {
            this.img = new Bitmap((int)this._GraphSize.Width, (int)this._GraphSize.Height);
            Guid[] ids = new Guid[this._Vertices.Count];
            this._Vertices.Keys.CopyTo(ids, 0);
            Random randomGen = new Random((int)DateTime.Now.Ticks);
            foreach (Guid id in ids)
            {
                Vertice v = this._Vertices[id];
                int x = randomGen.Next((int)this._GraphSize.Width);
                int y = randomGen.Next((int)this._GraphSize.Height);
                v.PosX = x;
                v.PosY = y;
            }
            this.verticeForces = new Dictionary<Guid, Vector>();
            this._IsStopped = false;
            if(asyncMode)
            {
                if(this._WorkerThread !=null && this._WorkerThread.IsAlive && 
                    this._WorkerThread.IsBackground)
                {
                    this._SyncObj.Close();
                    this._WorkerThread.Abort();
                    this._WorkerThread.Join();
                    this._SyncObj = new Mutex(false, "GraphLayout");
                }
                this._Iteration = 1;
                this._WorkerThread=new Thread(new ThreadStart(Iterate));
                this._WorkerThread.IsBackground = true;
                this._WorkerThread.Start();
            }
            else
            {
                this._Iteration = 1;
                this._WorkerThread = Thread.CurrentThread;
                this.Iterate();
            }
        }

        /// <summary>
        /// 
        /// </summary>
        public void StopRender()
        {
            this._IsStopped = true;

            if(this._WorkerThread!=null && 
                this._WorkerThread.IsAlive && 
                this._WorkerThread.IsBackground)
            {
                this._WorkerThread.Abort();
                this._WorkerThread.Join();
            }
            
            if (this.GraphLayoutFinished != null)
                this.GraphLayoutFinished();
        }

        /// <summary>
        /// 
        /// </summary>
        public void ContinueLayout()
        {
            if(this._IsStopped)
            {
                this._IsStopped = false;
                if (this._WorkerThread != null && this._WorkerThread.IsAlive)
                {
                    this._SyncObj.Close();
                    this._WorkerThread.Abort();
                    this._WorkerThread.Join();
                    this._SyncObj = new Mutex(false, "GraphLayout");
                }
                this._Iteration = 1;
                this._WorkerThread = new Thread(new ThreadStart(Iterate));
                this._WorkerThread.IsBackground = true;
                this._WorkerThread.Start();
            }
        }

        /// <summary>
        /// vertice got hightlight color (Darker or Lighter dependent on background color)
        /// label is displayed in bold font
        /// </summary>
        /// <param name="mousePos"></param>
        /// <returns></returns>
        public Vertice SelectVertice(PointF mousePos)
        {
            this._SyncObj.WaitOne();
			foreach (Vertice v in this._Vertices.Values)
			{
				v.CanMove = true;
			}
            this._SelectedVerticeIDs=new List<Guid>();
            RectangleF mouseBounds = new RectangleF(mousePos.X - 2, mousePos.Y - 2, 4, 4);
            foreach(Vertice v in this._Vertices.Values)
            {
                RectangleF bounds=new RectangleF(v.PosX-v.Width/2, v.PosY - v.Height /2, v.Width, v.Height);
                if(!RectangleF.Intersect(bounds, mouseBounds).IsEmpty)
                {
                    this._SelectedVerticeIDs.Add(v.ID);
                    v.CanMove = false;
                    break;
                }
            }
            this._SyncObj.ReleaseMutex();
            if (this._SelectedVerticeIDs != null && this._SelectedVerticeIDs.Count > 0)
            {
                if(this._IsStopped)
                {
                    this.UpdateImage();
                }
                return this._Vertices[this._SelectedVerticeIDs[0]];
            }
            else
                return null;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="v"></param>
        /// <param name="mousePos"></param>
        public void DragVertice(Vertice v, PointF mousePos)
        {
            if (v.CanDrag)
            {
                v.CanMove = false;
                v.PosX = mousePos.X;
                v.PosY = mousePos.Y;
                if (this._SelectedVerticeIDs == null)
                    this._SelectedVerticeIDs = new List<Guid>();
                if (!this._SelectedVerticeIDs.Contains(v.ID))
                    this._SelectedVerticeIDs.Add(v.ID);
                if (this._IsStopped)
                {
                    this.UpdateImage();
                }

                if(this._IsStopped)
                    this.ContinueLayout();
            }
        }

        /// <summary>
        /// clear any selected vertices or edges
        /// </summary>
        public void UnSelect()
        {
            if(this._SelectedVerticeIDs !=null && this._SelectedVerticeIDs.Count>0)
            {
                foreach(Guid selectedVID in this._SelectedVerticeIDs)
                {
                    if (this._Vertices.ContainsKey(selectedVID))
                        this._Vertices[selectedVID].CanMove = true;
                }
                this._SelectedVerticeIDs.Clear();
            }
            if(this._SelectedEdgeIDs !=null && this._SelectedEdgeIDs.Count>0)
            {
                this._SelectedEdgeIDs.Clear();
            }

            if (this._IsStopped)
            {
                this.UpdateImage();
            }
        }

        /// <summary>
        /// when edge is selected, both edge and its connected vertices got highlighted
        /// and label is displayed in bold font 
        /// </summary>
        /// <param name="mousePos"></param>
        /// <returns></returns>
        public Edge SelectEdge(PointF mousePos)
        {
            this._SelectedEdgeIDs=new List<Guid>();
            // TODO: point - line collision detection algorithm 
            return null;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="regionOfInterest"></param>
        public void Select(RectangleF regionOfInterest)
        {
            this._SyncObj.WaitOne();
            if (this._SelectedVerticeIDs != null && this._SelectedVerticeIDs.Count > 0)
            {
                foreach (Guid selectedVID in this._SelectedVerticeIDs)
                {
                    if (this._Vertices.ContainsKey(selectedVID))
                        this._Vertices[selectedVID].CanMove = true;
                }
            }
            this._SelectedVerticeIDs = new List<Guid>();
            foreach (Vertice v in this._Vertices.Values)
            {
                RectangleF bounds = new RectangleF(v.PosX - v.Width / 2, v.PosY - v.Height / 2, v.Width, v.Height);
                if (!RectangleF.Intersect(bounds, regionOfInterest).IsEmpty)
                {
                    this._SelectedVerticeIDs.Add(v.ID);
                }
            }
            if (this._IsStopped)
            {
                this.UpdateImage();
            }
            this._SyncObj.ReleaseMutex();
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="vIDs"></param>
        public void SelectVertices(List<Guid> vIDs)
        {
            this._SelectedVerticeIDs = vIDs;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="eIDs"></param>
        public void SelectEdges(List<Guid> eIDs)
        {
            this._SelectedEdgeIDs = eIDs;
        }

        #endregion

        #region draw
        private void Iterate()
        {
            if(this._IsStopped)
                return;
            if (this._Iteration > _MaxIterations)
            {
                this._IsStopped = true;
                if (this.GraphLayoutFinished != null)
                    this.GraphLayoutFinished();
                return;
            }

            this.UpdateForces();
            this.UpdatePositions();
            this.UpdateImage();

            this._Iteration++;
            this.Iterate();
        }
        #endregion

        #region Eades algorithm
        /// <summary>
        /// 
        /// </summary>
        /// <returns>if should continue</returns>
        private void UpdateForces()
        {
            //int bigMoves = 0;
            float repulsionRange = Math.Min(this._GraphSize.Width, this._GraphSize.Height) / 4;
            Guid[] vIDs=new Guid[this._Vertices.Count];
            this._Vertices.Keys.CopyTo(vIDs,0);
            Guid[] eIDs=new Guid[this._Edges.Count];
            this._Edges.Keys.CopyTo(eIDs,0);
            foreach (Guid vID in vIDs)
            {
                Vertice v = this._Vertices[vID];
                if (v.CanMove)
                {
                    double fX = 0;
                    double fY = 0;

                    // attracting force
                    foreach (Guid eId in eIDs)
                    {
                        Vertice v2 = null;
                        Edge edge = this._Edges[eId];
                        if (edge.VerticeID1 == edge.VerticeID2)
                            continue;
                        if (edge.VerticeID1 == v.ID)
                            v2 = this._Vertices[edge.VerticeID2];
                        else if (edge.VerticeID2 == v.ID)
                            v2 = this._Vertices[edge.VerticeID1];
                        double scaleFactor = 1.0;
                        if (v2 != null)
                        {
                            if (v.NetworkName == v2.NetworkName)
                            {
                                if (this._DistanceScaleFactor.ContainsKey(v.NetworkName))
                                    scaleFactor = this._DistanceScaleFactor[v.NetworkName];
                                else if (this._DistanceScaleFactor.ContainsKey(v2.NetworkName))
                                    scaleFactor = this._DistanceScaleFactor[v2.NetworkName];
                            }
                            else
                            {
                                foreach(NetworkJoin join in this._Graph.Joins)
                                {
                                    if((join.FromNetworkName==v.NetworkName && join.ToNetworkName==v2.NetworkName) || 
                                        (join.FromNetworkName==v2.NetworkName && join.ToNetworkName ==v.NetworkName))
                                    {
                                        if (this._DistanceScaleFactor2.ContainsKey(join))
                                            scaleFactor = this._DistanceScaleFactor2[join];
                                        break;
                                    }
                                }
                            }

                            double restingDistance = edge.Length * scaleFactor;
                        
                            double d =
                                Math.Sqrt(
                                    Math.Pow(v.PosX - v2.PosX, 2) +
                                    Math.Pow(v.PosY - v2.PosY, 2));
                            if (d > 0)
                            {
                                double forceConstant = SpringStiffness;
                                if (v.NetworkName == v2.NetworkName)
                                {
                                    forceConstant =
                                        this.Graph.Networks[v.NetworkName].AttractingForce;
                                }
                                else 
                                {
                                    foreach (NetworkJoin join in this.Graph.Joins)
                                    {
                                        if (join.FromNetworkName == v.NetworkName && join.ToNetworkName == v2.NetworkName)
                                        {
                                            forceConstant = join.AttractingForce;
                                            break;
                                        }
                                        else if (join.FromNetworkName == v2.NetworkName && join.ToNetworkName == v.NetworkName)
                                        {
                                            forceConstant = join.AttractingForce;
                                            break;
                                        }
                                    }
                                }
                                double fSpring = forceConstant * Math.Log(d / restingDistance);
                                fX += fSpring * (v2.PosX - v.PosX) / d;
                                fY += fSpring * (v2.PosY - v.PosY) / d;
                                //fX += SpringStiffness*(d - restingDistance)*((v2.PosX - v.PosX)/d);
                                //fY += SpringStiffness*(d - restingDistance)*((v2.PosY - v.PosY)/d);
                            }
                        }
                    }

                    // repeling force
                    foreach (Guid vID2 in vIDs)
                    {
                        Vertice v2 = this._Vertices[vID2];
                        if (v.ID != v2.ID && Math.Abs(v2.PosX - v.PosX) < repulsionRange &&
                            Math.Abs(v2.PosY - v.PosY) < repulsionRange)
                        {
                            double d =
                                Math.Sqrt(
                                    Math.Pow(v.PosX - v2.PosX, 2) +
                                    Math.Pow(v.PosY - v2.PosY, 2));
                            if (d > 0 && d<=this._DistanceThreshold)
                            {
                                double forceConstant2 = ElectronicRepulsionFactor;
                                if (v.NetworkName == v2.NetworkName)
                                {
                                    forceConstant2 =
                                        this.Graph.Networks[v.NetworkName].RepellingForce;
                                }
                                else 
                                {
                                    foreach (NetworkJoin join in this.Graph.Joins)
                                    {
                                        if (join.FromNetworkName == v.NetworkName && join.ToNetworkName == v2.NetworkName)
                                        {
                                            forceConstant2 = join.RepellingForce;
                                            break;
                                        }
                                        else if (join.FromNetworkName == v2.NetworkName && join.ToNetworkName == v.NetworkName)
                                        {
                                            forceConstant2 = join.RepellingForce;
                                            break;
                                        }
                                    }
                                }

                                fX += Math.Min(this._DistanceThreshold, Math.Pow(forceConstant2/d, 2)*((v.PosX - v2.PosX)/d));
                                fY += Math.Min(this._DistanceThreshold, Math.Pow(forceConstant2 / d, 2) * ((v.PosY - v2.PosY) / d));
                            }
                        }
                    }

                    double dampingFactor = ((double) this._MaxIterations - this._Iteration)/this._MaxIterations;
                    fX *= dampingFactor;
                    fY *= dampingFactor;
                    if (this.verticeForces.ContainsKey(v.ID))
                        this.verticeForces[v.ID] = new Vector(fX, fY);
                    else
                        this.verticeForces.Add(v.ID, new Vector(fX, fY));
                }
                else
                {
                    if (this.verticeForces.ContainsKey(v.ID))
                        this.verticeForces[v.ID] = new Vector();
                }
            }

            // crossing 
            //Random randForce=new Random();
            //int crossingProcessed = 0;
            //foreach(Edge e1 in this.Edges.Values)
            //{
            //    foreach(Edge e2 in this.Edges.Values)
            //    {
            //        if(e1.ID !=e2.ID && this.IsCrossing(e1,e2))
            //        {
            //            double x = this.verticeForces[e2.VerticeID1].X + randForce.Next(50) - 25;
            //            double y = this.verticeForces[e2.VerticeID1].Y + randForce.Next(50) - 25;
            //            this.verticeForces[e2.VerticeID1] = new Vector(x, y);
            //            crossingProcessed++;
            //        }
            //    }
            //    if(crossingProcessed>10)
            //        break;
            //}
        }

        private bool IsCrossing(Edge e1, Edge e2)
        {
            float p1x = this._Vertices[e1.VerticeID1].PosX;
            float p1y = this._Vertices[e1.VerticeID1].PosY;
            float p2x = this._Vertices[e1.VerticeID2].PosX;
            float p2y = this._Vertices[e1.VerticeID2].PosY;
            Range<float> r1x = new Range<float>(Math.Min(p1x, p2x), Math.Max(p1x, p2x));
            Range<float> r1y = new Range<float>(Math.Min(p1y, p2y), Math.Max(p1y, p2y));

            float p3x = this._Vertices[e2.VerticeID1].PosX;
            float p3y = this._Vertices[e2.VerticeID1].PosY;
            float p4x = this._Vertices[e2.VerticeID2].PosX;
            float p4y = this._Vertices[e2.VerticeID2].PosY;
            Range<float> r2x = new Range<float>(Math.Min(p3x, p4x), Math.Max(p3x, p4x));
            Range<float> r2y = new Range<float>(Math.Min(p3y, p4y), Math.Max(p3y, p4y));
            if (r1x.OverlapWith(r2x) && r1y.OverlapWith(r2y))
            {
                return true;
            }
            else
            {
                return false;
            }
        }

        private void UpdatePositions()
        {
            int posUpdated = 0;
            Guid[] ids = new Guid[this._Vertices.Count];
            this._Vertices.Keys.CopyTo(ids, 0);
            foreach (Guid id in ids)
            {
                Vertice v = this._Vertices[id];
                if (v.CanMove)
                {
                    double x = v.PosX;
                    double y = v.PosY;
                    if (this.verticeForces.ContainsKey(v.ID))
                    {
                        x += this.verticeForces[v.ID].X;
                        y += this.verticeForces[v.ID].Y;
                    }
                    if (x < 0)
                        x = 0;
                    if (x > this._GraphSize.Width)
                        x = this._GraphSize.Width;

                    if (y < 0)
                        y = 0;
                    if (y > this._GraphSize.Height)
                        y = this._GraphSize.Height;

                    if (Math.Abs(x - v.PosX) > 0.05 || Math.Abs(y - v.PosY) > 0.05)
                        posUpdated++;
                    v.PosX = (float) x;
                    v.PosY = (float) y;
                }
            }

            if(posUpdated==0)
            {
                this._IsStopped = true;
                if (this.GraphLayoutFinished != null)
                    this.GraphLayoutFinished();
            }
        }

        /// <summary>
        /// 
        /// </summary>
        public void UpdateImage()
        {
            Graphics graphics = Graphics.FromImage(this.img);
            graphics.Clear(this._BackColor);
            Font distanceFont=new Font(new FontFamily("Arial"), 6.5f);
            Brush distanceBrush = new SolidBrush(Color.FromArgb(100, Color.Black));
            Pen edgePen = new Pen(Color.FromArgb(100, Color.Brown), 2);
            SolidBrush arrowBrush = new SolidBrush(Color.FromArgb(100, Color.Brown));
            foreach (Edge e in this._Edges.Values)
            {
                Vertice v1 = this._Vertices[e.VerticeID1];
                Vertice v2 = this._Vertices[e.VerticeID2];
                PointF point1 = new PointF(v1.PosX, v1.PosY);
                PointF point2 = new PointF(v2.PosX, v2.PosY);
                if(e is Arc)
                {
                    double d = Math.Sqrt(Math.Pow(v1.PosX - v2.PosX, 2) + Math.Pow(v1.PosY - v2.PosY, 2));
                    double dX = Math.Abs(v1.PosX - v2.PosX)/d*v2.Width/2;
                    double dY = Math.Abs(v1.PosY - v2.PosY)/d*v2.Height/2;
                    if (point1.X < point2.X)
                    {
                        point2.X -= (float) dX;
                    }
                    else
                    {
                        point2.X += (float)dX;
                    }
                    if (point1.Y < point2.Y)
                    {
                        point2.Y -= (float) dY;
                    }
                    else
                    {
                        point2.Y += (float) dY;
                    }    
                }
                
                edgePen.Width = e.Thickness;
                if (e.LineStyle == EdgeLineStyle.Dashed)
                    edgePen.DashStyle = DashStyle.Dash;
                if (this._SelectedEdgeIDs.Contains(e.ID))
                {
                    edgePen.Color = this.GetHighlightColor(e.PenColor);
                }
                else
                {
                    edgePen.Color = e.PenColor;
                }
                edgePen.Color = Color.FromArgb(50,edgePen.Color);
                if(e is Arc)
                {
                    arrowBrush.Color = e.PenColor;
                    this.DrawArraw(graphics, edgePen, arrowBrush, point1, point2);
                }
                else
                {
                    graphics.DrawLine(edgePen, point1, point2);
                }
                if(this._ShowEdgeDistances || this._SelectedEdgeIDs.Contains(e.ID))
                {
                    float distancePosX = (point1.X + point2.X)/2;
                    float distancePosY = (point1.Y + point2.Y) / 2;
                    graphics.DrawString(e.Length.ToString(), distanceFont, distanceBrush, distancePosX, distancePosY);
                }
            }

            SolidBrush labelBrush = new SolidBrush(Color.FromArgb(175, Color.Black));
            //GraphicsPath gp=new GraphicsPath();
            
            foreach (Vertice v in this._Vertices.Values)
            {
                labelBrush.Color = Color.FromArgb(125, labelBrush.Color);
                if(!this._SelectedVerticeIDs.Contains(v.ID))
                    this.DrawVertice(graphics, labelBrush, v);
            }
            if(this._SelectedVerticeIDs !=null && this._SelectedVerticeIDs.Count>0)
            {
                foreach(Guid selectedVID in this._SelectedVerticeIDs)
                {
                    if (this._Vertices.ContainsKey(selectedVID))
                        this.DrawVertice(graphics, labelBrush, this._Vertices[selectedVID]);
                }
            }

            graphics.Dispose();

            if (this.GraphUpdated != null)
                this.GraphUpdated(this.img);
        }

        private void DrawArraw(Graphics graphics, Pen edgePen, Brush arrowBrush, PointF p1, PointF p2)
        {
            PointF[] aptArrowHead = new PointF[3];

            // set first node to terminal point            
            aptArrowHead[0] = p2;

            DrawingVector vecLine = new DrawingVector(p2.X - p1.X, p2.Y - p1.Y);// build the line vector
            DrawingVector vecLeft = new DrawingVector(-vecLine[1], vecLine[0]);// build the arrow base vector - normal to the line

            // setup remaining arrow head points
            float lineLength = vecLine.Length;
            float th = this._ArrowWidth / (2.0f * lineLength);
            float ta = this._ArrowWidth / (2.0f * ((float)Math.Tan(this._ArrowTheta / 2.0f)) * lineLength);

            // find the base of the arrow
            PointF pBase = new PointF(aptArrowHead[0].X + -ta * vecLine[0], aptArrowHead[0].Y + -ta * vecLine[1]); //base of the arrow

            // build the points on the sides of the arrow
            aptArrowHead[1] = new PointF(pBase.X + th * vecLeft[0], pBase.Y + th * vecLeft[1]);
            aptArrowHead[2] = new PointF(pBase.X + -th * vecLeft[0], pBase.Y + -th * vecLeft[1]);

            graphics.DrawLine(edgePen, p1, pBase); //master line

            graphics.FillPolygon(arrowBrush, aptArrowHead); //fill arrow head if desired

            graphics.DrawPolygon(edgePen, aptArrowHead); //draw outline
        }

        private void DrawVertice(Graphics graphics, Brush labelBrush, Vertice v)
        {
            //RectangleF bounds = new RectangleF(
            //    v.PosX - v.Width/2,
            //    v.PosY - v.Height/2,
            //    v.Width, v.Height);
            //gp.AddEllipse(bounds);
            //PathGradientBrush vBrush = new PathGradientBrush(gp);
            //vBrush.CenterPoint = v.Position;
            //vBrush.CenterColor = Color.WhiteSmoke;
            //vBrush.SurroundColors = new Color[] { v.VerticeColor };
            Color vColor = Color.FromArgb(
                        v.VerticeColorA,
                        v.VerticeColorR, v.VerticeColorG, v.VerticeColorB);
            Font labelFont = new Font(new FontFamily("Arial"), 8f);
            switch (v.VerticeShape)
            {
                case VerticeShape.Circle:
                    // cover edge drawing
                    graphics.FillEllipse(
                            new SolidBrush(this.BackgroundColor),
                            v.PosX - v.Width / 2,
                            v.PosY - v.Height / 2,
                            v.Width,
                            v.Height);


                    if (this._SelectedVerticeIDs.Contains(v.ID))
                    {
                        graphics.FillEllipse(
                            new SolidBrush(this.GetHighlightColor(vColor)),
                            v.PosX - v.Width / 2,
                            v.PosY - v.Height / 2,
                            v.Width,
                            v.Height);
                        //graphics.FillPath(vBrush, gp);
                    }
                    else
                    {
                        graphics.FillEllipse(
                            new SolidBrush(vColor),
                            v.PosX - v.Width / 2,
                            v.PosY - v.Height / 2,
                            v.Width,
                            v.Height);
                    }
                    break;
                case VerticeShape.UpTriangle:
                    // cover edge drawing
                    PointF a = new PointF(v.PosX, v.PosY - v.Height / 2);
                    PointF b = new PointF(v.PosX - v.Width / 2, v.PosY + v.Height / 2);
                    PointF c = new PointF(v.PosX + v.Width / 2, v.PosY + v.Height / 2);
                    graphics.FillPolygon(new SolidBrush(this.BackgroundColor), new PointF[] { a, b, c });

                    if (this._SelectedVerticeIDs.Contains(v.ID))
                        graphics.FillPolygon(
                            new SolidBrush(this.GetHighlightColor(vColor)),
                            new PointF[] { a, b, c });
                    else
                        graphics.FillPolygon(
                            new SolidBrush(vColor),
                            new PointF[] { a, b, c });
                    break;
                case VerticeShape.DownTrangle:
                    // cover edge drawing
                    PointF d = new PointF(v.PosX - v.Width / 2, v.PosY - v.Height / 2);
                    PointF e = new PointF(v.PosX + v.Width / 2, v.PosY - v.Height / 2);
                    PointF f = new PointF(v.PosX, v.PosY + v.Height / 2);
                    graphics.FillPolygon(new SolidBrush(this.BackgroundColor), new PointF[] { d, e, f });
                    if (this._SelectedVerticeIDs.Contains(v.ID))
                        graphics.FillPolygon(
                            new SolidBrush(this.GetHighlightColor(vColor)),
                            new PointF[] { d, e, f });
                    else
                        graphics.FillPolygon(
                            new SolidBrush(vColor),
                            new PointF[] { d, e, f });
                    break;
                case VerticeShape.Square:
                    // cover edge drawing
                    graphics.FillRectangle(
                        new SolidBrush(this.BackgroundColor),
                        new RectangleF(
                            v.PosX - v.Width / 2,
                            v.PosY - v.Height / 2,
                            v.Width,
                            v.Height));
                    if (this._SelectedVerticeIDs.Contains(v.ID))
                        graphics.FillRectangle(
                            new SolidBrush(this.GetHighlightColor(vColor)),
                            new RectangleF(
                            v.PosX - v.Width / 2,
                            v.PosY - v.Height / 2,
                            v.Width,
                            v.Height));
                    else
                        graphics.FillRectangle(
                            new SolidBrush(vColor),
                            new RectangleF(
                            v.PosX - v.Width / 2,
                            v.PosY - v.Height / 2,
                            v.Width,
                            v.Height));
                    break;
                case VerticeShape.Diamond:
                    // cover edge drawing
                    PointF p1 = new PointF(v.PosX - v.Width / 2, v.PosY);
                    PointF p2 = new PointF(v.PosX, v.PosY - v.Height / 2);
                    PointF p3 = new PointF(v.PosX + v.Width / 2, v.PosY);
                    PointF p4 = new PointF(v.PosX, v.PosY + v.Height / 2);
                    graphics.FillPolygon(new SolidBrush(this.BackgroundColor), new PointF[] { p1, p2, p3, p4 });
                    if (this._SelectedVerticeIDs.Contains(v.ID))
                        graphics.FillPolygon(
                            new SolidBrush(this.GetHighlightColor(vColor)),
                            new PointF[] { p1, p2, p3, p4 });
                    else
                        graphics.FillPolygon(
                            new SolidBrush(vColor),
                            new PointF[] { p1, p2, p3, p4 });
                    break;
            }

            if (this.ShowVerticeLabels || this._SelectedVerticeIDs.Contains(v.ID))
            {
                if (this._SelectedVerticeIDs.Contains(v.ID))
                {
                    labelFont = new Font(new FontFamily("Arial"), 9f, FontStyle.Bold);
                }
                float labelPosX = v.PosX + v.Width / 2;
                float labelPosY = v.PosY + v.Height / 2;
                graphics.DrawString(v.Label, labelFont, labelBrush, labelPosX, labelPosY);
            }
        }
        #endregion

        #region Fruchterman & Reingold algorithm

        #endregion

        #region highlight
        private Color GetHighlightColor(Color color)
        {
            int a = color.A;
            int r = (int)Math.Min(255, (int)(color.R + 100));
            int g = (int)Math.Min(255, (int)(color.G + 100));
            int b = (int)Math.Min(255, (int)(color.B + 100));
            return Color.FromArgb(a, r, g, b);
        }
        #endregion
    }
}
